
class Apriori:
	
	@classmethod
	def caculate(cls, dataSet, minSupport=0.5):
		C1 = cls.createC1(dataSet)
		# D = map(set, dataSet)
		L1, supportData = cls.scanD(dataSet, C1, minSupport)
		L = [L1]
		k = 2
		while (len(L[k - 2]) > 0):
			Ck = cls.aprioriGen(L[k - 2], k)
			Lk, supK = cls.scanD(dataSet, Ck, minSupport)
			supportData.update(supK)
			L.append(Lk)
			k += 1
		
		return L, supportData
	
	@classmethod
	def createC1(self, dataSet):
		C1 = []
		for transaction in dataSet:
			for item in transaction:
				if not [item] in C1:
					C1.append([item])
		C1.sort()
		return map(frozenset, C1)
	
	@classmethod
	def aprioriGen(cls, Lk, k):
		retList = []
		lenLk = len(Lk)
		for i in range(lenLk):
			for j in range(i + 1, lenLk):
				L1 = list(Lk[i])[: k - 2]
				L2 = list(Lk[j])[: k - 2]
				L1.sort()
				L2.sort()
				if L1 == L2:
					retList.append(Lk[i] | Lk[j])
		return retList
	
	@classmethod
	def scanD(self, D, Ck, minSupport):
		ssCnt = {}
		l_Ck = list(Ck)
		for tid in D:
			for can in l_Ck:
				if can.issubset(tid):
					if ssCnt.get(can) == None: ssCnt[can] = 1
					else: ssCnt[can] += 1
		numItems = float(len(D))
		retList = []
		supportData = {}
		for key in ssCnt:
			support = ssCnt[key]/numItems
			if support >= minSupport:
				retList.insert(0, key)
			else:
				#print(str(key) + "支持度：" + str(support)+ "，小于最小支持度：" + str(minSupport))
				pass
			supportData[key] = support
		return retList, supportData